The invention provides method and apparatus for identifying routes for nets.
An integrated circuit (xe2x80x9cICxe2x80x9d) is a device that includes many electronic components (e.g., transistors, resistors, diodes, etc.). These components are often interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit components of IC""s are jointly referred to below as xe2x80x9ccomponents.xe2x80x9d
An IC also includes multiple layers of wiring (xe2x80x9cwiring layersxe2x80x9d) that interconnect its electronic and circuit components. For instance, many IC""s are currently fabricated with metal or polysilicon wiring layers (collectively referred to below as xe2x80x9cmetal layersxe2x80x9d) that interconnect its electronic and circuit components. One common fabrication model uses five metal layers. In theory, the wiring on the metal layers can be all-angle wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is commonly referred to as Euclidean wiring. In practice, however, each metal layer typically has a preferred wiring direction, and the preferred direction alternates between successive metal layers. Many IC""s use the Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring. In this wiring model, the majority of the wires can only make 90xc2x0 turns. However, occasional diagonal jogs are sometimes allowed on the preferred horizontal and vertical layers.
Design engineers design IC""s by transforming circuit description of the IC""s into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (xe2x80x9cEDAxe2x80x9d) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.
EDA applications create layouts by using geometric shapes that represent different materials and devices on IC""s. For instance, EDA tools commonly use rectangular lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. For the sake of simplifying the discussion, these geometric objects are shown as rectangular blocks in this document.
Also, in this document, the phrase xe2x80x9ccircuit modulexe2x80x9d refers to the geometric representation of an electronic or circuit IC component by an EDA application. EDA applications typically illustrate circuit modules with pins on their sides. These pins connect to the interconnect lines.
A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a net list. In other words, a net list specifies a group of nets, which, in turn, specify the interconnections between a set of pins.
FIG. 1 illustrates an example of an IC layout 100. This layout includes five circuit modules 105, 110, 115, 120, and 125 with pins 130-160. Four interconnect lines 165-180 connect these modules through their pins. In addition, three nets specify the interconnection between the pins. Specifically, pins 135, 145, and 160 define a three-pin net, while pins 130 and 155, and pins 140 and 150 respectively define two two-pin nets. As shown in FIG. 1, a circuit module (such as 105) can have multiple pins on multiple nets.
The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; (5) compaction, which compresses the layout to decrease the total IC area; and (6) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a xe2x80x9cloosexe2x80x9d route (also called path or routing areas) for the interconnect lines that are to connect the pins of the net. The xe2x80x9cloosenessxe2x80x9d of a global route depends on the particular global router used. After global routes have been created, the detailed routing creates specific individual routing paths for each net.
While some commercial global routers today might allow an occasional diagonal jog, these routers do not typically explore diagonal routing paths consistently when they are specifying the routing geometries of the interconnect lines. This, in turn, increases the total wirelength (i.e., total length of interconnect lines) needed to connect the nets in the layout. Therefore, there is a need for routing method and apparatus that considers diagonal routing paths.
Some embodiments of the invention provide a method that identifies a set of routes for a net that has a set of pins in a region of a design layout. The method initially partitions the region into a number of sub-regions. It then identifies a first set of sub-regions that contains the net""s pins. The method next determines whether a storage structure stores a set of routes for the identified first set of sub-regions. If so, the method retrieves the set of routes. If not, the method generates a set of routes. In some embodiments, the method generates a set of routes by first identifying a connection set of sub-regions that when combined with the first set forms a closed set of sub-regions. The closed set of sub-regions does not have any sub-region that is not adjacent to another sub-region in the closed set. The storage structure stores a set of routes for the closed set. For the first set, the method then retrieves the set of routes that are stored for the closed set of sub-regions from the storage structure.